package solutions.leetcode.hard;

import solutions.lib.BaseSolution;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/largest-rectangle-in-histogram/">84. 柱状图中最大的矩形</a>
 */
public class Solution84 extends BaseSolution {

    public int largestRectangleArea(int[] heights) {
        class Model {
            final int height;
            int width;

            public Model(int height, int width) {
                this.height = height;
                this.width = width;
            }
        }

        int max = 0;
        List<Model> list = new LinkedList<>();
        for (int h : heights) {
            int width = 0;
            for (int i = list.size() - 1; i >= 0; i--) {
                Model model = list.get(i);
                if (model.height > h) {
                    list.remove(i);
                    max = Math.max(max, model.height * model.width);
                    width = model.width;
                } else {
                    break;
                }
            }
            if (h == 0) {
                continue;
            }
            if (list.isEmpty() || list.get(list.size() - 1).height < h) {
                list.add(new Model(h, width));
            }
            for (Model model : list) {
                model.width++;
            }
        }
        for (Model model : list) {
            max = Math.max(max, model.height * model.width);
        }

        return max;
    }

    public static void main(String[] args) {
        Solution84 solution = new Solution84();
        System.out.println(solution.largestRectangleArea(new int[] {
                2,1,2
        }));
    }
}